package 力扣.二分;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.List;

public class 模板 {
    /**
     * 注意左闭右开

      有序皆可用二分
     */
    boolean binarySearch(long[] A, long target) {
        if (A == null || A.length == 0){
            return false;
        }
        int l = 0,r = A.length;
        while (l < r){
            int mid = l + ((r - l) >> 1);
            if (A[mid] < target){
                l = mid + 1;
            }else if (A[mid] > target){
                r = mid;
            }else {
                return true;
            }
        }
        return false;
    }

    /**
     * '地板二分 && 天花板二分`完成二分搜索
     * @param A 数组
     * @param n 数组长度
     * @param target 目标值
     * @return
     */
    private boolean binarySearch2(int[] A,int n,int target){

/*        int l = lowerBound(A, n, target);//lowerBound
        return l < n && A[l] == target;//要么越界，要么不相等(不相等的具体位置参考力扣35题)
*/
        int l = upperBound(A, n, target);//upperBound
        l--;
        return l >= 0 && l < n && A[l] == target;//要么越界，要么不相等(不相等的具体位置参考力扣35题)
    }
    /**
     * 地板二分
     */
    private int lowerBound(int[] A,int n,int target){
        int l = 0,r = n;
        while (l < r){
            int mid = l + ((r - l) >> 1);
            if (A[mid] < target){
                l = mid + 1;
            }else {
                r = mid;
            }
        }
        return l;
    }

    /**
     * 天花板二分 注意会返回target的后一个位置元素。因此要减一位
     */
    private int upperBound(int[] A,int n,int target){
        int l = 0,r = n;
        while (l < r){
            int mid = l + ((r - l) >> 1);
            if (A[mid] <= target){
                l = mid + 1;
            }else {
                r = mid;
            }
        }
        return l;
    }


    public static void main(String[] args) {
        模板 this_Object = new 模板();
        List<Integer> integerList = Arrays.asList(1, 2, 3, 1, 3, 76, 8);
        Boolean isFound = this_Object.binarySearch(integerList.toArray(new Integer[integerList.size()]), 1);
        System.out.println(isFound);
    }


    private Boolean binarySearch(Integer[] ints , int target){
        if (ints == null || ints.length == 0){
            return false;
        }
        int l = 0,r = ints.length;
        while (l < r){
            int m = l + ((r - l) >> 1);
            if (ints[m] == target){
                return true;
            }
            if (ints[m] < target){
                l = m+1;
            }else{
                r = m;
            }
        }
        return false;
    }
}


